package cn.njupt.countSort;

import cn.njupt.cmpSort.Sort;

//基数排序适用于整数排序，尤其是非负整数,对个位数、十位数、百位数依次进行排序
public class RadixSort extends Sort<Integer> {
    @Override
    public void sort() {
        //个位数   i/1%10
        //百位数   i/10%10
        //千位数   i/100%10
        int max=array[0];
        for (int i = 1; i < array.length; i++) {
            max=Math.max(max,array[i]);
        }
        for (int i = 1; i <= max; i=i*10) {
            countSort(i);
        }
    }

    public void countSort(int num){
        //最大值为9，最小值为0
        int[] count=new int[10];

        for (int i = 0; i < array.length; i++) {
            count[array[i]/num%10]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i]+=count[i-1];
        }
        int[] target=new int[array.length];
        for (int i = array.length-1;i >=0; i--) {
            target[--count[array[i]/num%10]]=array[i];
        }
        for (int i = 0; i <array.length; i++) {
            array[i]= target[i];
        }

    }


}
